import java.util.*;

public class Array {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();

        if (nums != null && nums.length > 2) {
            // 先对数组进行排序
            Arrays.sort(nums);
            // i表示假设取第i个数作为结果
            for (int i = 0; i < nums.length - 2; ) {
                // 第二个数可能的起始位置
                int j = i + 1;
                // 第三个数可能是结束位置
                int k = nums.length - 1;

                while (j < k) {
                    // 如果找到满足条件的解
                    if (nums[j] + nums[k] == -nums[i]) {
                        // 将结果添加到结果含集中
                        List<Integer> list = new ArrayList<>(3);
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        result.add(list);

                        // 移动到下一个位置，找下一组解
                        k--;
                        j++;

                        // 从左向右找第一个与之前处理的数不同的数的下标
                        while (j < k && nums[j] == nums[j - 1]) {
                            j++;
                        }
                        // 从右向左找第一个与之前处理的数不同的数的下标
                        while (j < k && nums[k] == nums[k + 1]) {
                            k--;
                        }
                    }
                    // 和大于0
                    else if (nums[j] + nums[k] > -nums[i]) {
                        k--;
                        // 从右向左找第一个与之前处理的数不同的数的下标
                        while (j < k && nums[k] == nums[k + 1]) {
                            k--;
                        }
                    }
                    // 和小于0
                    else {
                        j++;
                        // 从左向右找第一个与之前处理的数不同的数的下标
                        while (j < k && nums[j] == nums[j - 1]) {
                            j++;
                        }
                    }
                }

                // 指向下一个要处理的数
                i++;
                // 从左向右找第一个与之前处理的数不同的数的下标
                while (i < nums.length - 2 && nums[i] == nums[i - 1]) {
                    i++;
                }
            }
        }
        return result;
    }

    public boolean increasingTriplet(int[] nums) {
        int len=nums.length;
        if(len<3)return false;
        for (int i=0;i<len-2;i++){
            for (int j=i+1;j<len-1;j++){
                for(int k=j+1;k<len;k++){
                    if(nums[i]<nums[j]&&nums[j]<nums[k])
                        return true;
                }
            }
        }
        return false;
    }
    public void setZeroes(int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int row[]=new int[m];
        int col[]=new int[n];
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if(matrix[i][j]==0){
                    row[i]=1;
                    col[j]=1;
                }
            }
        }
        for (int i=0;i<m;i++){
            if(row[i]==1){
                for (int j=0;j<n;j++){
                    matrix[i][j]=0;
                }
            }
        }
        for(int j=0;j<n;j++){
            if(col[j]==1){
                for (int i=0;i<m;i++){
                    matrix[i][j]=0;
                }
            }
        }
    }


    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result=new ArrayList<>();
        int len=strs.length;
        if(len==0){

        }else {
            HashMap<String,Integer> map=new HashMap<>();
            for(int i=0;i<len;i++){
                char []temp=strs[i].toCharArray();
                Arrays.sort(temp);
                String key="";
                for (int j=0;j<temp.length;j++){
                    key+=temp[j];
                }
                if(map.containsKey(key)){
                    int line=map.get(key);
                    result.get(line).add(strs[i]);
                }else {
                    int size=result.size();
                    map.put(key,size);
                    List<String> list=new ArrayList<>();
                    list.add(strs[i]);
                    result.add(list);
                }
            }
        }
        return result;
    }

    public String longestPalindrome(String s) {
        int len=s.length();
        int mov=2*len;
        int max=0;
        String result=s.charAt(0)+"";
        for(int i=0;i<mov;i++){
            int temp=0;
            if(i%2==0){
                temp=2;
            }else {
                temp=1;
            }
            int before=(i-temp)/2;
            int after=(i+temp)/2;
            while(before>=0&&after<len){
                if(s.charAt(before)==s.charAt(after)){
                    temp=temp+2;
                    before=(i-temp)/2;
                    after=(i+temp)/2;
                }else break;
            }
            if(max<(after-before-2)){
                max=after-before-2;
                result=s.substring(before+1,after);
            }

        }
        return result;
    }
}
